import math
import random

POINTS = [(1.83, 3.43), (1.17, 3.37), (1.23, 2.2), (2.67, 2.47), (2.67, 3.73), (2.43, 3.37), (2.23, 2.7), (1.97, 2.3),
          (1.53, 2.73), (1.97, 2.9), (1.97, 4.1), (1.33, 4.1), (1.63, 3.93), (1.1, 3.8), (1.43, 3.77), (1.6, 3.17),
          (1.2, 3.13), (0.83, 3.13), (0.9, 2.33), (1.0, 2.83), (4.27, 2.33), (3.93, 1.8), (4.03, 1.07), (4.73, 1.1),
          (4.8, 2.33), (4.27, 2.63), (3.6, 2.7), (3.67, 3.23), (3.1, 2.9), (2.83, 3.1), (3.6, 1.57), (3.47, 1.93),
          (4.07, 2.2), (3.83, 2.43), (4.67, 1.5), (4.3, 1.8), (4.63, 2.1), (4.73, 2.9), (4.63, 3.27), (1.4, 1.37),
          (1.77, 0.6), (2.63, 0.77), (2.67, 1.03), (2.33, 1.4), (1.77, 1.4), (1.77, 1.0), (2.13, 1.03), (1.2, 1.07),
          (1.2, 0.5), (1.67, 0.5), (1.67, 0.5), (2.4, 0.47), (3.13, 0.5), (3.07, 1.4), (2.47, 1.4), (2.33, 0.77),
          (1.6, 0.87), (1.53, 1.07), (1.53, 0.67), (2.23, 0.67), (2.3, 1.23)]


def distance(pt1, pt2):
    return math.sqrt(math.pow(pt2[0] - pt1[0], 2) + math.pow(pt2[1] - pt1[1], 2))


# 计算新的簇心点
def compute_new_centered_points(data, clustered_points):
    new_clustered_points = {}
    for cp in clustered_points:
        new_clustered_points[cp] = []

    # 按簇心点分类
    for x, y in data:
        min_distance = 0
        clustered_pt = None

        for cp_x, cp_y in clustered_points:
            dist = distance((x, y), (cp_x, cp_y))
            if clustered_pt is None:
                min_distance = dist
                clustered_pt = (cp_x, cp_y)
                continue

            if min_distance > dist:
                min_distance = dist
                clustered_pt = (cp_x, cp_y)

        new_clustered_points[clustered_pt].append((x, y))

    new_centered_points = []
    # 计算新的簇心
    for cp, points in new_clustered_points.items():
        new_x = sum([x for x, _ in points]) / len(points)
        new_y = sum([y for _, y in points]) / len(points)
        new_centered_points.append((new_x, new_y))

    return new_centered_points


def plot_data(data, cps):
    from matplotlib import pyplot as plt

    # for cp, points in dt.items():
    #     plt.scatter([x for x,_ in points], [y for _, y in points])
    #     plt.scatter([cp[0]], [cp[1]], color="red")

    plt.scatter([x for x, _ in data], [y for _, y in data])
    for cpx, cpy in cps:
        plt.scatter([cpx], [cpy])

    plt.show()


def k_mean(data, k, iterations=10):

    # 随机生成K个簇心点
    # 初始化指向第一个点
    # TODO: 优化
    min_x, max_x, min_y, max_y = data[0][0], data[0][0], data[0][1], data[0][1]
    for x, y in data:
        if min_x > x:
            min_x = x
        if max_x < x:
            max_x = x

        if min_y > y:
            min_y = y
        if max_y < y:
            max_y = y

    clustered_points = []
    for i in range(k):
        clustered_points.append(
            (random.randint(int(min_x), int(max_x + 1)), random.randint(int(min_y), int(max_y + 1))))

    # 迭代
    while True:
        exit_flag = True
        new_centered_points = compute_new_centered_points(data, clustered_points)

        for i in range(len(clustered_points)):
            dist = distance(new_centered_points[i], clustered_points[i])
            print(dist)
            if dist > 0:
                exit_flag = False
                break
        clustered_points = new_centered_points

        if exit_flag:
            return new_centered_points
        # if iterations <= 0:
        #     return new_centered_points
        # iterations -= 1


cp = k_mean(POINTS, 3)
plot_data(POINTS, cp)
